/*!
 * \file rdmaxclique.c
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Russian dolls algorithm for maximum clique.
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>

#include <bitmap.h>
#include <graph.h>
#include <grinput.h>
#include <heurPartiteSubgraph.h>
#include <mcr.h>

typedef struct {
	int vidx;
	int minRNode; //<! a lower bound for the node index of the smallest element in the set
	int maxRNode; //<! an upper bound for the node index of the greatest element in the set
	NODETYPE * R;
	int minWNode; //<! a lower bound for the node index of the smallest element in the set
	int maxWNode; //<! an upper bound for the node index of the greatest element in the set
	NODETYPE * W;
} Doll;

static int (*maxPartiteSubgraph)(NODETYPE *, NODETYPE *, int, int *, int *,
		int *, int *);

static int (*sortVertices)(Graph *, int *);

void rd_maxClique(Graph * g, int maxdeg, long long * ndolls, long long * memsz) {
	int n = g->n;
	int nnodes = NODEIDX(n-1) + 1;

#ifdef _SSE_
	int nbytes = nnodes*WSIZE;
	nbytes += (16 - (nbytes & 0xF));
	nnodes = nbytes/WSIZE;
#endif

	printf("nnodes=%d\n",nnodes);
	fflush(NULL);

	Doll stack[++maxdeg];
	Doll * doll = stack;
	*memsz = maxdeg * sizeof(Doll);

#ifdef _SSE_
	stack->R = (NODETYPE *) aligned_malloc((maxdeg << 1) * nnodes * WSIZE);
#else
	stack->R = (NODETYPE *) calloc((maxdeg << 1) * nnodes, WSIZE);
#endif
	*memsz += (maxdeg << 1) * nnodes * WSIZE;

	int i, q;
	for (i = 0, q = 0; i < maxdeg; doll++, i++, q += nnodes) {
		doll->R = stack->R + q;
		q += nnodes;
		doll->W = stack->R + q;
	}

#ifdef _SSE_
	nnodes = NODEIDX(n-1) + 1;
#endif

	ADDALL(stack->R, nnodes);
	stack->R[nnodes - 1] = RETAINLEAST(stack->R[nnodes-1],IDXINNODE(n-1)+1);

	doll = stack;

	doll->minRNode = minNode(doll->R, 0, nnodes - 1);
	doll->maxRNode = maxNode(doll->R, nnodes - 1, doll->minRNode);
	doll->minWNode = nnodes;
	doll->maxWNode = -1;
	int v = 0;

	initHeur(g);

	//initialize with a maximal clique
	if (g->maxcq < 0)
		g->maxcq = maxClique(doll->R, doll->minRNode, doll->maxRNode);

	printf("g-maxcq=%d\n", g->maxcq);
	fflush(NULL);

	//build a coloring of the size of the maximal clique found
	mcsColoring_f(doll->R, doll->W, g->maxcq, &doll->minRNode, &doll->maxRNode,
			&doll->minWNode, &doll->maxWNode);

	int curC[n]; //!< Current clique
	*memsz = n * sizeof(int);

	(*ndolls) = 1;
	if (doll->minRNode > doll->maxRNode)
		goto TERMINATE;

//	int bottomC = 0;
	int topC = 0;
	int vnode;

	int yesinstance;
	int yesv = 0;
	while (topC >= 0) {
//		printf("topC=%d\n",topC);
//		fflush(NULL);

		yesinstance = topC > g->maxcq;
		if (yesinstance) {
			yesv = curC[0];
			//eliminate a maximal stable set that contains sub->v
//			while (bottomC > 0 && doll->R[doll->minRNode])
//				maxStab(doll->R, doll->W, curC[bottomC--], &doll->minRNode, &doll->maxRNode, &doll->minWNode, &doll->maxWNode);
//			if (doll->R[doll->minRNode])
			maxStab(doll->R, doll->W, yesv, &doll->minRNode, &doll->maxRNode,
					&doll->minWNode, &doll->maxWNode);
//
//			//expand the current best clique
			int expc = topC;
			if (doll->R[doll->minRNode] != 0) {
				expc = expClique(doll->R, curC, doll->minRNode, doll->maxRNode,
						topC);
//				int e = maxCliqueWith(doll->R, doll->W, curC[0], doll->minRNode, doll->maxRNode, doll->minWNode, doll->maxWNode);
//				if (e > expc)
//					expc = e;
				mcsColoring_f(doll->R, doll->W, expc - g->maxcq - 1,
						&doll->minRNode, &doll->maxRNode, &doll->minWNode,
						&doll->maxWNode);

//				int l, nout = 0;
//				for (l=expc-1; l>=g->maxcq; l--)
//					if (!ISINNODE(doll->W[NODEIDX(curC[l])], IDXINNODE(curC[l])))
//							nout++;
////				if (nout > 0)
//					printf("################################# nout=%d maxcq=%d expc=%d\n",nout,g->maxcq,expc);
			}
			g->maxcq = expc;
			topC = 0;
		}

		if (doll->R[doll->minRNode] == 0) {
			if (doll == stack) {
				doll->minRNode = minNode(doll->R, doll->minRNode, doll->maxRNode);
				if (doll->minRNode > doll->maxRNode	|| (doll->minRNode == doll->maxRNode && doll->R[doll->minRNode] == 0))
					topC--;
			} else {
				doll--;
//				if (topC == bottomC)
//					bottomC--;
				topC--;
			}
		} else {
			//get the next vertex in the candidate set
			vnode = doll->minRNode;
			if (doll == stack) {
				NODETYPE buf = (NEIG(g, yesv)[vnode] & doll->R[vnode]);
				while (!buf && ++vnode < doll->maxRNode)
					buf = (NEIG(g, yesv)[vnode] & doll->R[vnode]);
				if (buf)
					doll->vidx = NODELEAST(buf);
				else {
					vnode = doll->minRNode;
					doll->vidx = NODELEAST(doll->R[vnode]);
				}
			} else
				doll->vidx = NODELEAST(doll->R[vnode]);

			v = doll->vidx + NELEM(vnode);
			if (topC == g->maxcq) {
//				if (topC == bottomC && !doll->R[doll->minRNode])
//					bottomC++;
				doll = stack;
				curC[topC++] = v;
			} else {
				doll->R[vnode] = DELFROMNODE(doll->R[vnode], doll->vidx);
				doll->W[vnode] = ADDTONODE(doll->W[vnode], doll->vidx);
				if (vnode > doll->maxWNode)
					doll->maxWNode = vnode;
				if (vnode < doll->minWNode)
					doll->minWNode = vnode;
				doll->minRNode = minNode(doll->R, doll->minRNode, doll->maxRNode);

				//Calculate the new candidate vector
				Doll * subdoll = doll + 1;
				intersectOf(subdoll->R, NEIG(g, v), doll->W, doll->minWNode, doll->maxWNode + 1);
				subdoll->minRNode = minNode(subdoll->R, doll->minWNode,	doll->maxWNode);
				subdoll->maxRNode = maxNode(subdoll->R, doll->maxWNode,	subdoll->minRNode);

				//Check if the candidate vector is not empty
				if (subdoll->minRNode <= subdoll->maxRNode) { // && cardOfSet(subdoll->R, subdoll->minRNode, subdoll->maxRNode+1) >= max-topC-1) {
					DELALL(subdoll->W+subdoll->minRNode, subdoll->maxRNode-subdoll->minRNode+1);
					subdoll->minWNode = nnodes;
					subdoll->maxWNode = -1;

					//Build a coloring for the candidate's vector
					if (maxPartiteSubgraph(subdoll->R, subdoll->W,
							g->maxcq - topC - 1, &subdoll->minRNode,
							&subdoll->maxRNode, &subdoll->minWNode,
							&subdoll->maxWNode) == g->maxcq - topC - 1) {
//						if (bottomC == 0 || (topC == bottomC && !doll->R[doll->minRNode]))
//							bottomC++;
						doll = subdoll;
						curC[topC++] = v;
					}
					(*ndolls)++;
				}
			}
		}
	}

	TERMINATE:

	*memsz += getMemSize();
#ifdef _SSE_
	aligned_free(stack->R);
#else
	free(stack->R);
#endif

	closeHeur();
}

int main(int argc, char *argv[]) {
	char name[200];
	FILE* graphFile = NULL;
	FILE* outFile = NULL;

	outFile = fopen(argv[1], "a+");
	graphFile = fopen(argv[2], "r");
	strcpy(name, argv[2]);
	int algo;
	if (argc >= 4)
		algo = atoi(argv[3]);
	else
		algo = 1;

	switch (algo) {
	case 1: {
		maxPartiteSubgraph = greedyColoring;
		break;
	}
	case 2: {
		maxPartiteSubgraph = mcsColoring;
		break;
	}
	case 3: {
		printf("Not implemented.\n");
		exit(0);
		break;
	}
	case 4: {
		maxPartiteSubgraph = fracColoring;
		break;
	}
	}

	int order;
	if (argc >= 5)
		order = atoi(argv[4]);
	else
		order = 1;

	switch (order) {
	case 1: {
		sortVertices = mcr;
		break;
	}
	case 2: {
		sortVertices = heapMcr;
		break;
	}
	case 3: {
		sortVertices = decDegree;
		break;
	}
	case 4: {
		sortVertices = decExdegree;
		break;
	}
	}

	Graph * g = readDimacsGraph(graphFile);

	struct timeval tvoi, tvoe;
	float renumberTime;

	int maxdeg;
	gettimeofday(&tvoi, NULL);
	int R[g->n];
	maxdeg = sortVertices(g, R);

	printf("maxdeg=%d\n",maxdeg);
	fflush(NULL);

	Graph * gg = newRenumbered(g, R);
	gettimeofday(&tvoe, NULL);

	printf("renumbered ok\n");
	fflush(NULL);

	renumberTime = (tvoe.tv_sec - tvoi.tv_sec) + (tvoe.tv_usec - tvoi.tv_usec) / 1000000000.0;
	delGraph(g);
	free(g);

	gg->maxcq = -1;
	if (argc >= 6)
	{
		char * fnm = strstr(argv[2], "random/");
		if (fnm != NULL)
		{
			fnm = strchr(fnm, '/')+1;
		}
		else
		{
			fnm = strrchr(argv[2], '/');
			if (fnm == NULL)
				fnm = argv[2];
			else
				fnm = fnm + 1;
		}
		fnm = strtok(fnm, ".");

		FILE * maxFile = fopen(argv[5], "r");
		char linestr[100];
		char * solfilename;
		while (!feof(maxFile) && gg->maxcq < 0)
		{
			fgets(linestr, 100, maxFile);
			solfilename = strtok(linestr, " ");
			int maxcq = atoi(strtok(NULL, " "));
			if (!strcmp(fnm, solfilename))
			{
				gg->maxcq = maxcq;
				printf("%s %d\n", solfilename, gg->maxcq);
			}
		}
		fclose(maxFile);
	}

	long long memsz;
	long long ndolls;

	struct timespec start, end;
	struct timeval tvs, tve;
	float optimizationTime;

	gettimeofday(&tvs, NULL);
	rd_maxClique(gg, maxdeg, &ndolls, &memsz);
	gettimeofday(&tve, NULL);
	start.tv_sec = tvs.tv_sec;
	start.tv_nsec = tvs.tv_usec * 1000;
	end.tv_sec = tve.tv_sec;
	end.tv_nsec = tve.tv_usec * 1000;
	optimizationTime = (end.tv_sec - start.tv_sec);
	optimizationTime += (end.tv_nsec - start.tv_nsec) / 1000000000.0;

	printf(
			"%s \t n=%d  colorHeur=%d  sortVert=%d  sol=%d  initTime=%f  ndolls=%lld  time=%f  mem=%fKB  graphmem=%fKB \n",
			name, gg->n, algo, order, gg->maxcq, renumberTime, ndolls,
			optimizationTime, memsz / 1024.0, gg->matrixsize / 1024.0);
	fprintf(outFile,
			"%s \t %d \t %d \t %d \t %d \t %f \t %lld \t %f \t %f \t %f\n",
			name, gg->n, algo, order, gg->maxcq, renumberTime, ndolls,
			optimizationTime, memsz / 1024.0, gg->matrixsize / 1024.0);
	fclose(outFile);
	fclose(graphFile);
	delGraph(gg);
	free(gg);
	return 0;
}
